The present invention pertains generally to the field of packet data networks and, more particularly, to system architectures and methods for controlling the quality of service and system stability in a packet data router.
In a typical packet data router, packets originating from various source locations are received via a plurality of communication interfaces. Each packet contains routing information, such as a destination address, which is associated with a respective communication interface of the router, e.g., by a routing table or packet forwarding protocol. The router reads the routing information of each received packet and, if it recognizes the information, forwards the packet to the appropriate communication interface for further transmission to its destination. Packets without known destination address or forwarding protocol information are typically dropped.
Due to normal ebbs and flows in packet data traffic patterns and volume, a packet data router may be unable to immediately route newly received packets to respective designated communication interfaces. In particular, packet data traffic tends to have bursts of high activity, which is followed by lulls. Thus, a packet data router may be characterized as having a sustained data rate and a burst data rate. When receiving a burst of packet traffic, the router will temporarily store the received packets in an associated memory until it has the processing capacity available to process and forward the packets to their respective outgoing communication interface. When the sustained or burst data rates of a router are exceeded for a certain period of time, it is inevitable that further incoming packets will be dropped. Of course, while sometimes unavoidable, dropping unprocessed packets is undesirable because the source will then retransmit the dropped packet as part of its recovery procedure, which tends to prolong the congested state of the packet router and cause further unprocessed packets to be dropped.
Packet data network users often share either a single router, or router system, from a service provider. Multiple different internet users, for example, may connect via respective data modems or primary rate interface (xe2x80x9cPRIxe2x80x9d) lines to a single internet protocol (xe2x80x9cIPxe2x80x9d) router, or IP router system, operated by an internet service provider (xe2x80x9cISPxe2x80x9d). These end users may be single customers themselves, or there may be multiple (e.g., networked) users combined as a single customer account by the ISP. Each customer account may be allocated a respective level of service priority and packet throughput bandwidth by the ISP, depending on the type and level of service connectivity that is contracted for.
For purposes of clarification, as referred to herein, a xe2x80x9crouterxe2x80x9d is defined as a physical (as opposed to logical) entity having a defined number of physical communication interfaces (e.g., modems) under the control of one or more processors collectively executing a single control function. Typically, a single physical router operates under a single routing domainxe2x80x94i.e., wherein a packet received on any communication interface may be forwarded only to the same, or any other communication interface of the router. As referred to herein, a xe2x80x9crouter systemxe2x80x9d is defined as two or more independent routers, with an external controller for selectively directing common (incoming) packet data traffic to respective routers within the system.
It is known to implement within a single router one or more virtual router instances (xe2x80x9cVRIsxe2x80x9d). Each VRI has its own subset of communication interfaces, or logical circuits on a shared communication interface, and its own routing domain, but still under the control of a common control function with the other packet traffic handled by the router. In particular, a VRI exists as a collection of processes performed by the router, which correspond roughly to the layers in the TCP/IP protocol model. For example, a private network can be configured as a VRI, so that packet data may only be exchanged between end users on the same network. It has also been proposed to have a single VRI span multiple routers in a router system. For example, one suggested implementation is to have a dedicated interface link bridging respective communication interfaces of multiple routers having a common VRI.
Because of varying and often unpredictable growth rates, as well as other economic factors, a packet router, or packet router system, will not necessarily have the processing or memory capacity to simultaneously provide the contracted for bandwidth allocation for every user or VRI it services. Further, various users will connect to the IP router at different, often unpredictable, times and with varying rates and bandwidth needs.
An IP router is typically controlled with a real time operating system (xe2x80x9cRTOSxe2x80x9d), which allows multiple processes of different priorities to co-exist under the control of a common control function (e.g., within a single central processing unit). For example, the RTOS may have sensors that provide feedback information regarding current usage characteristics for a given user, which is used to adjust the RTOS operating parameters in response to changes in demand. Common applications for the RTOS are process control, motion control and, in certain applications, command and control.
The problem is that these operating systems often fail to effectively accommodate the different priority and bandwidth requirements contracted for by the end user customers of the ISP. In a motion control system, for example, the flow of information from sensors is into the system, and the flow of control signals is out of the system. There may be a lot of sensors, and there may be a lot of subsystems being controlled, but the input information does not circulate through the system and become the output. This has the effect of making the inherent control feature of the RTOS process/task priority ineffectual for controlling the system.
In particular, a typical IP router is a xe2x80x9cpacket drivenxe2x80x9d system. The more data packet it receives, the greater the load, and that load traverses the whole system such that the input is (for all practical purposes) the output. Thus, users whose connection to the router is handling the most packets will tend to monopolize the system resources.
For example, consider a router that is divided into two different VRIs, with each VRI having roughly the same number of end users and paying an ISP for the same quality of service (xe2x80x9cQOSxe2x80x9d), including identical priority and bandwidth requirements. Thus, the router should be able to provide the end users of each VRI with the same number of bits-per-second (xe2x80x9cBPSxe2x80x9d) system throughput at any given time. Suppose, however, that the router processing capability is barely adequate to handle the peak load of even one of the VRIs without dropping unprocessed packets. If users of the first VRI have, in effect, tied up the router throughput processing capabilities, the users of the second VRI will not receive the service priority and bandwidth they are otherwise entitled to.
Thus, there is a need for methods and system architectures for more fairly regulating the processing of data packets through a packet data router, or router system, whereby the quality of service is balanced for each user and/or VRI, and wherein the system is kept stable, even when heavy loads occur.
In accordance with a first aspect of the invention, a method is provided for controlling packet data traffic in a router having a plurality of virtual router instances (xe2x80x9cVRIsxe2x80x9d), by dynamically adjusting the respective rates at which packets held in one or more ingress data queues associated with one or more VRIs are processed in response to current operating conditions of the router.
Preferably, the respective packet flow rates of the ingress data queues associated with the each VRI are independently adjusted. By way of example, in a preferred embodiment, the packet flow rates of the one or more ingress data queues associated with a first virtual router instance are decreased, and the packet flow rates of the one or more ingress data queues associated with the second virtual router instance are increased, respectively, in response to the same current operating conditions of the router.
In accordance with another aspect of the invention, a method is provided for controlling packet data traffic in a router having one or more processors collectively executing a single control function and having a processor utilization during operation of the router, the router further having a plurality of virtual router instances (xe2x80x9cVRIsxe2x80x9d), by dynamically adjusting the respective rates at which packets held in one or more ingress data queues associated with one or more VRIs are processed in response to current processor utilization of the router. Again, the respective packet flow rates of the ingress data queues associated with the each VRI are preferably independently adjusted.
By way of example, in a preferred embodiment, the packet flow rates of the one or more ingress data queues associated with a first VRI are decreased, and the packet flow rates of the one or more ingress data queues associated with the second VRI are increased, respectively, in response to the same processor utilization.
In accordance with yet another aspect of the invention, the packet flow rates of the one or more ingress data queues associated with one or more VRIs are periodically adjusted in order to maintain processor utilization, or memory utilization, or both, within a selected operating range.
In accordance with a still further aspect of the invention, the amount of memory allocated for storing packets in each of the one or more ingress data queues associated with one or more VRIs is periodically adjusted in order to maintain utilization of a memory associated with the router within a selected operating range.
As will be apparent to those skilled in the art, other and further aspects and advantages of the present invention will appear hereinafter.